<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=9"/>
<meta name="generator" content="Doxygen 1.8.13"/>
<meta name="viewport" content="width=device-width, initial-scale=1"/>
<title>OpenMesh: Mesh Iterators and Circulators</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="jquery.js"></script>
<script type="text/javascript" src="dynsections.js"></script>
<link href="navtree.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="resize.js"></script>
<script type="text/javascript" src="navtreedata.js"></script>
<script type="text/javascript" src="navtree.js"></script>
<script type="text/javascript">
  $(document).ready(initResizable);
</script>
<link href="search/search.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="search/searchdata.js"></script>
<script type="text/javascript" src="search/search.js"></script>
<link href="doxygen.css" rel="stylesheet" type="text/css" />
<link href="logo_align.css" rel="stylesheet" type="text/css"/>
</head>
<body>
<div id="top"><!-- do not remove this div, it is closed by doxygen! -->
<div id="titlearea">
<table cellspacing="0" cellpadding="0">
 <tbody>
 <tr style="height: 56px;">
  <td id="projectlogo"><img alt="Logo" src="rwth_vci_rgb.jpg"/></td>
  <td id="projectalign" style="padding-left: 0.5em;">
   <div id="projectname">OpenMesh
   </div>
  </td>
 </tr>
 </tbody>
</table>
</div>
<!-- end header part -->
<!-- Generated by Doxygen 1.8.13 -->
<script type="text/javascript">
var searchBox = new SearchBox("searchBox", "search",false,'Search');
</script>
<script type="text/javascript" src="menudata.js"></script>
<script type="text/javascript" src="menu.js"></script>
<script type="text/javascript">
$(function() {
  initMenu('',true,false,'search.php','Search');
  $(document).ready(function() { init_search(); });
});
</script>
<div id="main-nav"></div>
</div><!-- top -->
<div id="side-nav" class="ui-resizable side-nav-resizable">
  <div id="nav-tree">
    <div id="nav-tree-contents">
      <div id="nav-sync" class="sync"></div>
    </div>
  </div>
  <div id="splitbar" style="-moz-user-select:none;" 
       class="ui-resizable-handle">
  </div>
</div>
<script type="text/javascript">
$(document).ready(function(){initNavTree('a04328.html','');});
</script>
<div id="doc-content">
<!-- window showing the filter options -->
<div id="MSearchSelectWindow"
     onmouseover="return searchBox.OnSearchSelectShow()"
     onmouseout="return searchBox.OnSearchSelectHide()"
     onkeydown="return searchBox.OnSearchSelectKey(event)">
</div>

<!-- iframe showing the search results (closed by default) -->
<div id="MSearchResultsWindow">
<iframe src="javascript:void(0)" frameborder="0" 
        name="MSearchResults" id="MSearchResults">
</iframe>
</div>

<div class="header">
  <div class="headertitle">
<div class="title">Mesh Iterators and Circulators </div>  </div>
</div><!--header-->
<div class="contents">
<div class="textblock"><ul>
<li><a class="el" href="a04328.html#it_iters">Iterators</a></li>
<li><a class="el" href="a04328.html#it_iters_h">How to use iterators in OpenMesh</a></li>
<li><a class="el" href="a04328.html#it_iters_skipping">Skipping Iterators</a></li>
<li><a class="el" href="a04328.html#it_circs">Circulators</a></li>
<li><a class="el" href="a04328.html#it_circs_h">How to use circulators in OpenMesh</a></li>
</ul>
<h1><a class="anchor" id="it_iters"></a>
Iterators</h1>
<p>The mesh provides linear iterators (that enumerate vertices, halfedges, edges, and faces). These can be used to easily navigate through a mesh. Each iterator <code>XYZIter</code> also exists in a const version <code>ConstXYZIter</code>.</p>
<p>All iterators are defined in the namespace <a class="el" href="a01235.html" title="Contains all mesh iterators and circulators. ">OpenMesh::Iterators</a>. They are template classes that expect a mesh as template argument to be fully specified. You should use the iterator types provided by the mesh itself, i.e. <code>MyMesh::VertexIter</code> instead of <code>OpenMesh::Iterators::VertexIterT&lt;MyMesh&gt;</code>.</p>
<p>The iterators are:</p>
<div class="fragment"><div class="line">MyMesh mesh;</div><div class="line"></div><div class="line"><span class="comment">// iterate over all vertices</span></div><div class="line"><span class="keywordflow">for</span> (MyMesh::VertexIter v_it=mesh.vertices_begin(); v_it!=mesh.vertices_end(); ++v_it) </div><div class="line">   ...; <span class="comment">// do something with *v_it, v_it-&gt;, or *v_it</span></div><div class="line"></div><div class="line"><span class="comment">// iterate over all halfedges</span></div><div class="line"><span class="keywordflow">for</span> (MyMesh::HalfedgeIter h_it=mesh.halfedges_begin(); h_it!=mesh.halfedges_end(); ++h_it) </div><div class="line">   ...; <span class="comment">// do something with *h_it, h_it-&gt;, or *h_it</span></div><div class="line"></div><div class="line"><span class="comment">// iterate over all edges</span></div><div class="line"><span class="keywordflow">for</span> (MyMesh::EdgeIter e_it=mesh.edges_begin(); e_it!=mesh.edges_end(); ++e_it) </div><div class="line">   ...; <span class="comment">// do something with *e_it, e_it-&gt;, or *e_it</span></div><div class="line"></div><div class="line"><span class="comment">// iterator over all faces</span></div><div class="line"><span class="keywordflow">for</span> (MyMesh::FaceIter f_it=mesh.faces_begin(); f_it!=mesh.faces_end(); ++f_it) </div><div class="line">   ...; <span class="comment">// do something with *f_it, f_it-&gt;, or *f_it</span></div><div class="line"></div></div><!-- fragment --><p>The corresponding <code>const</code> counterparts are</p>
<ul>
<li><code>ConstVertexIter</code>, </li>
<li><code>ConstHalfedgeIter</code>, </li>
<li><code>ConstEdgeIter</code>, </li>
<li><code>ConstFaceIter</code>.</li>
</ul>
<p>The linear iterators are conformant to STL iterators. For a description of their interface see OpenMesh::Concepts::IteratorT.</p>
<p>When using iterators, use the pre-increment operation (++it) for efficiency reasons.</p>
<dl class="deprecated"><dt><b><a class="el" href="a01227.html#_deprecated000001">Deprecated:</a></b></dt><dd>While it is possible to use <code>handle()</code> to get the handle of the item referred to by the iterator, this function is deprecated. Simply dereference the iterator instead.</dd></dl>
<h2><a class="anchor" id="deletedElements"></a>
Deleted Elements</h2>
<p>If no elements of a mesh are marked as deleted, the indices provided by <code>idx()</code> are consecutive numbers from 0 to <em>number of elements</em>-1 (in the case of vertices this would be from 0 to n_vertices()-1).</p>
<p>However, note that this is <b>not</b> the case when elements are marked as deleted and <a class="el" href="a02113.html#aba7fd4df59227f974b44111ac45e835f" title="garbage collection ">OpenMesh::ArrayKernel::garbage_collection()</a> has not yet been called.</p>
<p>After garbage_collection() has been called the elements are reorganized and their handles and iterators are guaranteed to be consecutive numbers again.</p>
<p><a class="el" href="a01233.html" title="Contains all the mesh ingredients like the polygonal mesh, the triangle mesh, different mesh kernels ...">OpenMesh</a> uses a lazy deletion scheme to avoid unnecessary updates to the data structure. The halfedge data structure will always be updated directly to ensure that following algorithms will have the correct iterator setups.</p>
<p>So if you delete a face, The face itself will still exist but the halfedges which are now located at the hole will be updated directly, which means that circulators on the adjacent vertices will not come across the face anymore.</p>
<p>If an edge is deleted, the adjacent faces will be removed as well (flagging them deleted and updating the surrounding halfedges). The edge itself will also be flagged as deleted. Again the circulators will not see the deleted primitives anymore.</p>
<p>For a vertex, all adjacent faces and edges are deleted with the schemes above and the vertex flagged as deleted.</p>
<p>The iterators, going across vertices edges and faces will still enumerate all primitives (including deleted ones). Except if you use the skipping iterators, which will skip deleted primitives. The circulators always only enumerate primitives which are not deleted.</p>
<dl class="section note"><dt>Note</dt><dd><ul>
<li>
If you delete elements on the mesh, they will still be enumerated by the standard iterators. To skip deleted elements, use the <a class="el" href="a04328.html#it_iters_skipping">Skipping Iterators</a> </li>
<li>
An iterator to an item usually needs more memory than a handle of an item. To store many references to an item, it is therefore better to use handles. </li>
</ul>
</dd></dl>
<h1><a class="anchor" id="it_iters_h"></a>
How to use iterators in OpenMesh</h1>
<p>This example shows how to iterate over all faces of a mesh:</p>
<div class="fragment"><div class="line">MyMesh mesh;</div><div class="line"></div><div class="line"><span class="keywordflow">for</span>(MyMesh::FaceIter f_it = mesh.faces_begin(); f_it != mesh.faces_end(); ++f_it) {</div><div class="line">    std::cout &lt;&lt; <span class="stringliteral">&quot;The face&#39;s valence is &quot;</span> &lt;&lt; mesh.valence( *f_it ) &lt;&lt; std::endl;</div><div class="line">}</div></div><!-- fragment --><h1><a class="anchor" id="it_iters_skipping"></a>
Skipping Iterators</h1>
<p>All iterators are also available as skipping iterators. If elements are deleted on a mesh, the standard iterators go over all elements, even deleted ones(which are available until a garbage_collection is done). The skipping iterators ignore these elements. You can retrieve a skipping iterator by calling one of the following functions:</p>
<ul>
<li><code>vertices_sbegin()</code>, </li>
<li><code>edges_sbegin()</code>, </li>
<li><code>halfedges_sbegin()</code>, </li>
<li><code>faces_sbegin()</code> </li>
</ul>
<p>The ends for these iterators are equal to the standard iterator ends (e.g. <code>vertices_end()</code> ).</p>
<h1><a class="anchor" id="it_circs"></a>
Circulators</h1>
<p>OpenMesh also provides so called Circulators that provide means to enumerate items adjacent to another item of the same or another type. For example, a <code>VertexVertexIter</code> allows to enumerate all vertices immediately adjacent to a (center) vertex (i.e. it allows to enumerate the so-called 1-ring of the center vertex). Analogously, a <code>FaceHalfedgeIter</code> enumerates all the halfedges belonging to a face. In general, <code>CenterItem_AuxiliaryInformation_TargetItem_Iter</code> designates a circulator that enumerates all the target items around a given center item.</p>
<p>The constructor of a circulator is of the form <code>Circulator(MeshType mesh, TargetHandle center_handle)</code>, i.e. it takes a mesh and the handle of the item to circulate around.</p>
<p>The circulators around a vertex are:</p>
<ul>
<li><code>VertexVertexIter:</code> iterate over all neighboring vertices. </li>
<li><code>VertexIHalfedgeIter:</code> iterate over all <em>incoming</em> halfedges. </li>
<li><code>VertexOHalfedgeIter:</code> iterate over all <em>outgoing</em> halfedges. </li>
<li><code>VertexEdgeIter:</code> iterate over all incident edges. </li>
<li><code>VertexFaceIter:</code> iterate over all adjacent faces.</li>
</ul>
<p>The circulators around a face are:</p>
<ul>
<li><code>FaceVertexIter:</code> iterate over the face's vertices. </li>
<li><code>FaceHalfedgeIter:</code> iterate over the face's halfedges. </li>
<li><code>FaceEdgeIter:</code> iterate over the face's edges. </li>
<li><code>FaceFaceIter:</code> iterate over all edge-neighboring faces.</li>
</ul>
<p>Other circulators: </p><ul>
<li><code>HalfedgeLoopIter:</code> iterate over a sequence of Halfedges. (all Halfedges over a face or a hole)</li>
</ul>
<p>All circulators provide the operations listed in CirculatorT&lt;Mesh&gt;, which are basically the same as the iterator funtions.</p>
<dl class="section note"><dt>Note</dt><dd>Circulators are similar to bidirectional iterators and therefore they have the bidirectional_iterator_tag. However, the bidirectional requires that the attribute <a class="el" href="a01238.html#ab78a93560926cd2f9958cb028f7ea96dafaaebe1808b5cce96ad4e19df471d58a" title="Add storage for previous halfedge (halfedges). The bit is set by default in the DefaultTraits. ">OpenMesh::Attributes::PrevHalfedge</a> is available. Otherwise it is just a forward iterator.</dd></dl>
<dl class="deprecated"><dt><b><a class="el" href="a01227.html#_deprecated000002">Deprecated:</a></b></dt><dd>While it is possible to use <code>operator</code> <code>bool()</code>, which returns true, as long as the circulator hasn't reached the end of the sequence, this function is deprecated. Use the function <code>is_valid()</code> instead.</dd></dl>
<p>OpenMesh provides the following functions (defined in <a class="el" href="a02313.html" title="Connectivity Class for polygonal meshes. ">OpenMesh::PolyConnectivity</a>) to get circulators around a specified center item:</p>
<div class="fragment"><div class="line"><span class="comment">/**************************************************</span></div><div class="line"><span class="comment"> * Vertex circulators</span></div><div class="line"><span class="comment"> **************************************************/</span></div><div class="line"></div><div class="line"><span class="comment">// Get the vertex-vertex circulator (1-ring) of vertex _vh</span></div><div class="line">VertexVertexIter <a class="code" href="a02313.html#a6417ffb5839b4db58955533ee79c5a7f">OpenMesh::PolyConnectivity::vv_iter</a> (VertexHandle _vh);</div><div class="line"></div><div class="line"><span class="comment">// Get the vertex-incoming halfedges circulator of vertex _vh</span></div><div class="line">VertexIHalfedgeIter <a class="code" href="a02313.html#addc0f67e3818aaa4945c6f1dd2ef5837">OpenMesh::PolyConnectivity::vih_iter</a> (VertexHandle _vh);</div><div class="line"></div><div class="line"><span class="comment">// Get the vertex-outgoing halfedges circulator of vertex _vh</span></div><div class="line">VertexOHalfedgeIter <a class="code" href="a02313.html#a88be7595c00d8acda4b884974a423932">OpenMesh::PolyConnectivity::voh_iter</a> (VertexHandle _vh);</div><div class="line"></div><div class="line"><span class="comment">// Get the vertex-edge circulator of vertex _vh</span></div><div class="line">VertexEdgeIter <a class="code" href="a02313.html#ae43c9c12b88b32d80b21d2fdf00a0a6c">OpenMesh::PolyConnectivity::ve_iter</a> (VertexHandle _vh);</div><div class="line"></div><div class="line"><span class="comment">// Get the vertex-face circulator of vertex _vh</span></div><div class="line">VertexFaceIter <a class="code" href="a02313.html#af92290b9627d280953cf36754ce601d4">OpenMesh::PolyConnectivity::vf_iter</a> (VertexHandle _vh);</div><div class="line"></div><div class="line"><span class="comment">/**************************************************</span></div><div class="line"><span class="comment"> * Face circulators</span></div><div class="line"><span class="comment"> **************************************************/</span></div><div class="line"></div><div class="line"><span class="comment">// Get the face-vertex circulator of face _fh</span></div><div class="line">FaceVertexIter <a class="code" href="a02313.html#aeb868a647517e60a02d1e20f9a256da9">OpenMesh::PolyConnectivity::fv_iter</a> (FaceHandle _fh);</div><div class="line"></div><div class="line"><span class="comment">// Get the face-halfedge circulator of face _fh</span></div><div class="line">FaceHalfedgeIter <a class="code" href="a02313.html#ae313e747578a6dbd1de6d0a5ee5e3ad6">OpenMesh::PolyConnectivity::fh_iter</a> (FaceHandle _fh);</div><div class="line"></div><div class="line"><span class="comment">// Get the face-edge circulator of face _fh</span></div><div class="line">FaceEdgeIter <a class="code" href="a02313.html#a981b430e0ff7b2028e959fa8b0f5a306">OpenMesh::PolyConnectivity::fe_iter</a> (FaceHandle _fh);</div><div class="line"></div><div class="line"><span class="comment">// Get the face-face circulator of face _fh</span></div><div class="line">FaceFaceIter <a class="code" href="a02313.html#a406c75147195e212a7321b8697bb2d77">OpenMesh::PolyConnectivity::ff_iter</a> (FaceHandle _fh);</div></div><!-- fragment --><p>Additionally to the normal circulators there exists some for each direction (clock-wise, counterclock-wise). Those circulators might be slower than the normal one, but the direction of circulation is guaranteed. You can get these types of circulators by adding the infix "ccw" or "cw" to the function used to request the circulator of an item after the underscore. Example:</p>
<div class="fragment"><div class="line">VertexVertexIter vvit = mesh.vv_iter(some_vertex_handle);          <span class="comment">// fastest (clock or counterclockwise)</span></div><div class="line">VertexVertexCWIter vvcwit = mesh.vv_cwiter(some_vertex_handle);    <span class="comment">// clockwise</span></div><div class="line">VertexVertexCCWIter vvccwit = mesh.vv_ccwiter(some_vertex_handle); <span class="comment">// counter-clockwise</span></div></div><!-- fragment --><p>It is also possible to convert a cw circulator to a ccw circulator and vice versa. For this purpose, each circulator provides a constructor taking the other circulator as input. If a cw circulator is converted, the ccw circulator points on the same element as the cw circulator pointed on, but the direction for the increment and decrement changed.<br />
The conversion is only valid for valid circulators. The resulting circulator from a invalid circulator is still invalid, but might behave in a fashion not expected by normal iterators. Example: </p><div class="fragment"><div class="line">VertexVertexCWIter vvcwit = mesh.vv_cwend(some_vertex_handle);</div><div class="line">VertexVertexCCWIter vvccwit = VertexVertexCCWIter(vvcwit); <span class="comment">//conversion of an invalid circulator</span></div><div class="line"> --vvcwit;  <span class="comment">//is valid now (if the range &gt;= 1)</span></div><div class="line"> ++vvccwit; <span class="comment">//can still be invalid</span></div></div><!-- fragment --><p>CW and CCW circulators requires that <a class="el" href="a01238.html#ab78a93560926cd2f9958cb028f7ea96dafaaebe1808b5cce96ad4e19df471d58a" title="Add storage for previous halfedge (halfedges). The bit is set by default in the DefaultTraits. ">OpenMesh::Attributes::PrevHalfedge</a> is available.</p>
<dl class="section note"><dt>Note</dt><dd>For every circulator there also exists a constant version. To make use of these constant circulators just add the prefix<br />
 "Const" to the type specifier and add the prefix "c" to the function used to request the circulator of an item. Example:<br />
</dd></dl>
<div class="fragment"><div class="line">ConstVertexVertexIter cvvit = mesh.cvv_iter(some_vertex_handle);</div></div><!-- fragment --><dl class="section note"><dt>Note</dt><dd>When constructing Circulators from iterators, make sure you don't create a circulator of an deleted element(e.g. FaceVertexiter of a deleted Face), as this will lead to unpredictable behaviour. Using skipping iterators for iterating over the elements and creating circulators from them is safe as they don't contain deleted elements.</dd></dl>
<h1><a class="anchor" id="it_circs_h"></a>
How to use circulators in OpenMesh</h1>
<p>The following code example now shows how to enumerate the 1-ring of each vertex:</p>
<div class="fragment"><div class="line">MyMesh mesh;</div><div class="line"></div><div class="line"><span class="comment">// (linearly) iterate over all vertices</span></div><div class="line"><span class="keywordflow">for</span> (MyMesh::VertexIter v_it=mesh.vertices_sbegin(); v_it!=mesh.vertices_end(); ++v_it)</div><div class="line">{</div><div class="line">  <span class="comment">// circulate around the current vertex</span></div><div class="line">  <span class="keywordflow">for</span> (<a class="code" href="a02389.html#adc7d422e2ce13141e8291f7d29f7ecef">MyMesh::VertexVertexIter</a> vv_it=mesh.vv_iter(*v_it); vv_it.is_valid(); ++vv_it)</div><div class="line">  {</div><div class="line">    <span class="comment">// do something with e.g. mesh.point(*vv_it)</span></div><div class="line">  }</div><div class="line">}</div></div><!-- fragment --><p>Enumerating all halfedges adjacent to a certain face (the inner halfedges) is accomplished as follows:</p>
<div class="fragment"><div class="line">MyMesh mesh;</div><div class="line"></div><div class="line">...</div><div class="line"></div><div class="line"><span class="comment">// Assuming faceHandle contains the face handle of the target face</span></div><div class="line"></div><div class="line">MyMesh::FaceHalfedgeIter fh_it = mesh.fh_iter(faceHandle);</div><div class="line"></div><div class="line"><span class="keywordflow">for</span>(; fh_it.is_valid(); ++fh_it) {</div><div class="line">    std::cout &lt;&lt; <span class="stringliteral">&quot;Halfedge has handle &quot;</span> &lt;&lt; *fh_it &lt;&lt; std::endl;</div><div class="line">}</div></div><!-- fragment --> </div></div><!-- contents -->
</div><!-- doc-content -->
<hr>
<address>
<small>
<a href="http://www.rwth-graphics.de" style="text-decoration:none;">
</a>
Project <b>OpenMesh</b>, 
&copy;&nbsp; Computer Graphics Group, RWTH Aachen.
Documentation generated using 
<a class="el" href="http://www.doxygen.org/index.html">
<b>doxygen</b>
</a>.
</small>
</address>
</body>
</html>
